Авторы |
Мельников Борис Феликсович, доктор физико-математических наук, профессор, кафедра прикладной математики и информатики,Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), barmaley62@yandex.ru
Пивнева Светлана Валентиновна, кандидат педагогических наук, доцент, кафедра высшей математики и математического моделирования, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), tlt.swetlana@rambler.ru
Трифонов Максим Андреевич, аспирант, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), trifonov_max@mail.ru
|
Аннотация |
Актуальность и цели. Часто требуется измерить различие или расстояние между двумя строками (например, в эволюционных, структуральных или функциональных исследованиях биологических строк). Так как строковые последовательности митохондриальных ДНК приблизительно составляют 17 000 символов {a, g, c, t}, то для решения поставленной задачи были выбраны алгоритмы нечеткого сравнения, рассчитывающие расстояние за полиноминальное время. В рамках исследования при расчете метрик различными ранее известными алгоритмами неточного сравнения строк были получены различные результаты. Цель исследования: разработка методов качественной оценки полученных результатов. Разработка качественных оценок позволит сделать выбор более приемлемого алгоритма, что улучшит исследования в различных предметных областях.
Материалы и методы. В качестве метода исследования применятся теория треугольной нормы в метрическом пространстве.
Результаты. Исходные данные были получены из банка данных NCBI и случайным образом выбраны 30 строковых последовательностей митохондриальных ДНК. В результате работы алгоритмов сравнения 30 строковых последовательностей приведены качественные оценки.
Выводы. По полученным качественным оценкам метрик был определен наилучший алгоритм сравнения строковых последовательностей.
|
Список литературы |
1. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология / Д. Гасфилд. – СПб. : Невский диалект, БХВ-Петербург, 2003. – 654 с.
2. Бойцов, Л. Использование хеширования по сигнатуре для поиска по сходству /Л. Бойцов // Прикладная математика и информатика. – 2000. – № 7.
3. Мельников, Б. Ф. Параллельная реализация мультиэвристического подхода в задаче сравнения генетических последовательностей / Б. Ф. Мельников, А. Г. Панин // Вектор науки Тольяттинского государственного университета. – 2012. - № 4 (22). – С. 83–86.
4. NCBI: nucleotide database, 2015. – URL: http://www.ncbi.nlm.nih.gov/nuccore.
5. Пивнева, С. В. Моделирование задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов // Вектор науки Тольяттинского государственного университета. – 2010. – № 3. – С. 28–30.
6. Мельников, Б. Ф. Кластеризация ситуаций и принятие решений в задачах дискретной оптимизации / Б. Ф. Мельников, Е. А. Мельникова // Известия высших учебных заведений. Поволжский регион. Сер. Естественные науки. – 2007. –№ 2. – С. 25–28.
7. Сайфу ллина, Е. Ф. Об алгоритмах восстановления графа по вектору степеней второго порядка / Е. Ф. Сайфуллина, Р. И. Семенов // Эвристические алгоритмы и распределенные вычисления. – 2014. – Т. 1, № 2. – С. 43–57.
8. Needleman, S. A general method applicable to the search for simi-larities in the amino acid sequence of two proteins / S. Needleman, C. Wunsch // Journal of Molecular Bi-ology. – 1970. – № 48 (3). – P. 443–453.
9. Winkler, W. String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage / W. Winkler // Proceedings of the Section on Survey Research Methods. – American Statistical Association, 1990. – P. 354–359.
10. Ewing, B. Base-calling of automated sequencer traces using phred. I. Accuracy assessment/ B. Ewing, L. Hillier, M. Wendl, Р. Green // Genome Res. – 1998. – № 8 (3). –P. 175–185.
11. Altschul, S. F. Amino acid substitution matrices from an information theoretic perspective / S. F. Altschul // Journal of Molecular Biology. – 1991. – № 219 (3). –P. 555–565.
|